{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Binary Tree from Preorder and Postorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #array #hash-table #divide-and-conquer #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #数组 #哈希表 #分治 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: constructFromPrePost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根据前序和后序遍历构造二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数数组，<code>preorder</code>&nbsp;和 <code>postorder</code> ，其中 <code>preorder</code> 是一个具有 <strong>无重复</strong> 值的二叉树的前序遍历，<code>postorder</code> 是同一棵树的后序遍历，重构并返回二叉树。</p>\n",
    "\n",
    "<p>如果存在多个答案，您可以返回其中 <strong>任何</strong> 一个。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/07/24/lc-prepost.jpg\" style=\"height: 265px; width: 304px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]\n",
    "<strong>输出：</strong>[1,2,3,4,5,6,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> preorder = [1], postorder = [1]\n",
    "<strong>输出:</strong> [1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= preorder.length &lt;= 30</code></li>\n",
    "\t<li><code>1 &lt;= preorder[i] &lt;= preorder.length</code></li>\n",
    "\t<li><code>preorder</code>&nbsp;中所有值都 <strong>不同</strong></li>\n",
    "\t<li><code>postorder.length == preorder.length</code></li>\n",
    "\t<li><code>1 &lt;= postorder[i] &lt;= postorder.length</code></li>\n",
    "\t<li><code>postorder</code>&nbsp;中所有值都 <strong>不同</strong></li>\n",
    "\t<li>保证 <code>preorder</code>&nbsp;和 <code>postorder</code>&nbsp;是同一棵二叉树的前序遍历和后序遍历</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-binary-tree-from-preorder-and-postorder-traversal](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-binary-tree-from-preorder-and-postorder-traversal](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,4,5,3,6,7]\\n[4,5,2,6,7,3,1]', '[1]\\n[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.valtoIndex={}\r\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\r\n",
    "        for i in range(len(postorder)):\r\n",
    "            self.valtoIndex[postorder[i]]=i\r\n",
    "        return self.build(preorder,0,len(preorder)-1,postorder,0,len(postorder)-1)\r\n",
    "    \r\n",
    "    def build(self,preorder,prestart,preend,postorder,poststart,postend):\r\n",
    "        if prestart>preend:\r\n",
    "            return \r\n",
    "        if prestart==preend:\r\n",
    "            return TreeNode(preorder[prestart])\r\n",
    "        \r\n",
    "        rootVal=preorder[prestart]\r\n",
    "        leftrootval=preorder[prestart+1]\r\n",
    "        index=self.valtoIndex[leftrootval]\r\n",
    "\r\n",
    "        leftsize=index-poststart+1\r\n",
    "        root=TreeNode(rootVal)\r\n",
    "        root.left=self.build(preorder,prestart+1,prestart+leftsize,postorder,poststart,index)\r\n",
    "        root.right=self.build(preorder,prestart+leftsize+1,preend,postorder,index+1,postend-1)\r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:\n",
    "        if not pre and not post:\n",
    "            return None\n",
    "        if pre[0]==post[0]:\n",
    "            return TreeNode(pre[0])\n",
    "        root = TreeNode(pre[0])\n",
    "        i,j=1,0\n",
    "        while pre[i]!=post[j]:\n",
    "            j+=1\n",
    "        root.left=self.constructFromPrePost(pre[1:j+2],post[0:j+1])\n",
    "        root.right=self.constructFromPrePost(pre[j+2:],post[j+1:-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return None\n",
    "        root = TreeNode(val=preorder[0])\n",
    "        if len(preorder) == 1: return root\n",
    "        i = postorder.index(preorder[1]) + 1\n",
    "        root.left = self.constructFromPrePost(preorder[1:i+1], postorder[:i])\n",
    "        root.right = self.constructFromPrePost(preorder[i+1:], postorder[i:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode(preorder[0])\n",
    "        for node in preorder[1:]:\n",
    "            last = None\n",
    "            cur = root\n",
    "            nxt = None\n",
    "            while cur:\n",
    "                if postorder.index(node) < postorder.index(cur.val):\n",
    "                    last = cur\n",
    "                    cur = last.left\n",
    "                    nxt = last.right\n",
    "                elif postorder.index(node) > postorder.index(cur.val):\n",
    "                    cur = nxt\n",
    "            if last.left == None: last.left = TreeNode(node)\n",
    "            else: last.right = TreeNode(node)\n",
    "            \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def __init__(self):\r\n",
    "        # 存储 postorder 中值到索引的映射\r\n",
    "        self.valToIndex = {}\r\n",
    "\r\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:\r\n",
    "        for i in range(len(postorder)):\r\n",
    "            self.valToIndex[postorder[i]] = i\r\n",
    "        return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)\r\n",
    "\r\n",
    "    # 根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd] 构建二叉树，并返回根节点。\r\n",
    "    def build(self, preorder: List[int], preStart: int, preEnd: int, postorder: List[int], postStart: int, postEnd: int) -> TreeNode:\r\n",
    "        if preStart > preEnd:\r\n",
    "            return None\r\n",
    "        if preStart == preEnd:\r\n",
    "            return TreeNode(preorder[preStart])\r\n",
    "\r\n",
    "        # root 节点对应的值就是前序遍历数组的第一个元素\r\n",
    "        rootVal = preorder[preStart]\r\n",
    "        # root.left 的值是前序遍历第二个元素\r\n",
    "        # 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点\r\n",
    "        # 确定 preorder 和 postorder 中左右子树的元素区间\r\n",
    "        leftRootVal = preorder[preStart + 1]\r\n",
    "        # leftRootVal 在后序遍历数组中的索引\r\n",
    "        index = self.valToIndex[leftRootVal]\r\n",
    "        # 左子树的元素个数\r\n",
    "        leftSize = index - postStart + 1\r\n",
    "\r\n",
    "        # 先构造出当前根节点\r\n",
    "        root = TreeNode(rootVal)\r\n",
    "        # 递归构造左右子树\r\n",
    "        # 根据左子树的根节点索引和元素个数推导左右子树的索引边界\r\n",
    "        root.left = self.build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index)\r\n",
    "        root.right = self.build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1)\r\n",
    "\r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)\n",
    "\n",
    "\n",
    "    # 根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd] 构建二叉树，并返回根节点。\n",
    "    def build(self, preorder: List[int], preStart: int, preEnd: int, postorder: List[int], postStart: int, postEnd: int) -> TreeNode:\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        if preStart == preEnd:\n",
    "            return TreeNode(preorder[preStart])\n",
    "\n",
    "        # root 节点对应的值就是前序遍历数组的第一个元素\n",
    "        rootVal = preorder[preStart]\n",
    "        # root.left 的值是前序遍历第二个元素\n",
    "        # 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点\n",
    "        # 确定 preorder 和 postorder 中左右子树的元素区间\n",
    "        leftRootVal = preorder[preStart + 1]\n",
    "        # leftRootVal 在后序遍历数组中的索引\n",
    "        index = postorder.index(leftRootVal)\n",
    "        # 左子树的元素个数\n",
    "        leftSize = index - postStart + 1\n",
    "\n",
    "        # 先构造出当前根节点\n",
    "        root = TreeNode(rootVal)\n",
    "        # 递归构造左右子树\n",
    "        # 根据左子树的根节点索引和元素个数推导左右子树的索引边界\n",
    "        root.left = self.build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index)\n",
    "        root.right = self.build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.valToIndex = {}\n",
    "        \n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        for i in range(len(postorder)):\n",
    "            self.valToIndex[postorder[i]]=i\n",
    "        return self.build(preorder,0,len(preorder)-1,postorder,0,len(postorder)-1)\n",
    "    \n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        \n",
    "        rootVal = preorder[preStart]\n",
    "        root = TreeNode(rootVal)\n",
    "        if preStart == preEnd:\n",
    "            return root\n",
    "        \n",
    "        # 后序序列中左子树的根节点的index\n",
    "        index = self.valToIndex[preorder[preStart+1]]\n",
    "        leftSize = index - postStart + 1\n",
    "        root.left = self.build(preorder, preStart+1, preStart + leftSize, postorder, postStart, index)\n",
    "        root.right = self.build(preorder, preStart + leftSize+1, preEnd, postorder, index+1,postEnd-1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return\n",
    "        root = TreeNode(val = preorder[0])\n",
    "        preorderL = None\n",
    "        preorderR = None\n",
    "        postorderL = None\n",
    "        postorderR = None\n",
    "        restPreorder = preorder[1:]\n",
    "        restPostorder = postorder[:-1]\n",
    "        if len(restPreorder) == 1:\n",
    "            root.left = TreeNode(restPreorder[0])\n",
    "            return root\n",
    "        for i in range(1, len(restPreorder) + 1):\n",
    "            if set(restPreorder[:i]) == set(restPostorder[:i]) and\\\n",
    "            set(restPreorder[i:]) == set(restPostorder[i:]):\n",
    "                preorderL = restPreorder[:i]\n",
    "                postorderL = restPostorder[:i]\n",
    "                preorderR = restPreorder[i:]\n",
    "                postorderR = restPostorder[i:]\n",
    "                break\n",
    "        # print(preorderL, preorderR)\n",
    "        # print(postorderL, postorderR)\n",
    "        root.left = self.constructFromPrePost(preorderL, postorderL)\n",
    "        root.right = self.constructFromPrePost(preorderR, postorderR)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder or not postorder:\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(preorder.pop(0))\n",
    "        postorder.pop()\n",
    "\n",
    "        if preorder and preorder[0] == postorder[-1]:\n",
    "            root.left = self.constructFromPrePost(preorder, postorder)\n",
    "        elif preorder:\n",
    "            l_len = postorder.index(preorder[0]) + 1\n",
    "            root.left = self.constructFromPrePost(preorder[:l_len], postorder[:l_len])\n",
    "            root.right = self.constructFromPrePost(preorder[l_len:], postorder[l_len:])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.preindex, self.posindex = 0, 0\n",
    "\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode(preorder[self.preindex])\n",
    "        self.preindex += 1\n",
    "        if postorder[self.posindex] != root.val:\n",
    "            root.left = self.constructFromPrePost(preorder, postorder)\n",
    "        if postorder[self.posindex] != root.val:\n",
    "            root.right = self.constructFromPrePost(preorder, postorder)\n",
    "        self.posindex += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return None\n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1: return node\n",
    "        idx = postorder.index(preorder[1])\n",
    "        node.left = self.constructFromPrePost(preorder[1:idx+2], postorder[:idx+1])\n",
    "        node.right = self.constructFromPrePost(preorder[idx+2:], postorder[idx+1:-1])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        tree = TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return tree\n",
    "        i = postorder.index(preorder[1])\n",
    "        left_pre = preorder[1:i+2]\n",
    "        left_post = postorder[:i+1]\n",
    "        right_pre = preorder[i+2:]\n",
    "        right_post = postorder[i+1:-1]\n",
    "        # print(left_pre,left_post,right_pre,right_post)\n",
    "        tree.left = self.constructFromPrePost(left_pre,left_post)\n",
    "        tree.right = self.constructFromPrePost(right_pre,right_post)\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        root = TreeNode(preorder[0])\n",
    "        left_count = postorder.index(preorder[1])+1\n",
    "        root.left = self.constructFromPrePost(preorder[1:left_count+1],postorder[:left_count])\n",
    "        root.right = self.constructFromPrePost(preorder[left_count+1:],postorder[left_count:-1])\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, pre: List[int], post: List[int]) -> Optional[TreeNode]:\n",
    "        if not pre: return None\n",
    "        root = TreeNode(pre[0])\n",
    "        if len(pre) == 1: return root\n",
    "\n",
    "        L = post.index(pre[1]) + 1\n",
    "        root.left = self.constructFromPrePost(pre[1:L+1], post[:L])\n",
    "        root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        if not preorder:\n",
    "            return\n",
    "        root = TreeNode(preorder[0])\n",
    "        #拆分左右\n",
    "        L = postorder.index(preorder[1]) #左子树结束位置\n",
    "        #递归左右\n",
    "        leftroot = self.constructFromPrePost(preorder[1:L+2], postorder[:L+1])\n",
    "        rightroot = self.constructFromPrePost(preorder[L+2:], postorder[L+1:-1])\n",
    "        #连接左右\n",
    "        root.left = leftroot\n",
    "        root.right = rightroot\n",
    "        return root\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "\n",
    "        L = postorder.index(preorder[1]) + 1\n",
    "        root.left = self.constructFromPrePost(preorder[1:L + 1], postorder[:L])\n",
    "        root.right = self.constructFromPrePost(preorder[L + 1:], postorder[L : -1])\n",
    "\n",
    "        return root\n",
    "        #不能取到-1，因为postorder[-1]是根结点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return None\n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1: return node\n",
    "        idx = postorder.index(preorder[1])\n",
    "        node.left = self.constructFromPrePost(preorder[1:idx+2], postorder[:idx+1])\n",
    "        node.right = self.constructFromPrePost(preorder[idx+2:], postorder[idx+1:-1])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.val2Index = {}\n",
    "\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        for i in range(len(postorder)):\n",
    "            self.val2Index[postorder[i]] = i\n",
    "        print(self.val2Index)\n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder) - 1)\n",
    "    \n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        if preStart > preEnd:\n",
    "            return\n",
    "        if preStart == preEnd:\n",
    "            return TreeNode(preorder[preStart])\n",
    "        rootVal = preorder[preStart]\n",
    "        rootLeftVal = preorder[preStart + 1]\n",
    "        leftIndex = self.val2Index[rootLeftVal]\n",
    "        leftSize = leftIndex - postStart + 1\n",
    "        root = TreeNode(rootVal)\n",
    "        root.left = self.build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, leftIndex)\n",
    "        root.right = self.build(preorder, preStart + leftSize + 1, preEnd, postorder, leftIndex + 1, postEnd - 1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1: return root\n",
    "\n",
    "        L = postorder.index(preorder[1]) + 1\n",
    "        root.left = self.constructFromPrePost(preorder[1:L+1], postorder[:L])\n",
    "        root.right = self.constructFromPrePost(preorder[L+1:], postorder[L:-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.valToIndex = {}\n",
    "        \n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        for i in range(len(postorder)):\n",
    "            self.valToIndex[postorder[i]]=i\n",
    "        return self.build(preorder,0,len(preorder)-1,postorder,0,len(postorder)-1)\n",
    "    \n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        \n",
    "        rootVal = preorder[preStart]\n",
    "        root = TreeNode(rootVal)\n",
    "        if preStart == preEnd:\n",
    "            return root\n",
    "        \n",
    "        # 后序序列中左子树的根节点的index\n",
    "        index = self.valToIndex[preorder[preStart+1]]\n",
    "        leftSize = index - postStart + 1\n",
    "        root.left = self.build(preorder, preStart+1, preStart + leftSize, postorder, postStart, index)\n",
    "        root.right = self.build(preorder, preStart + leftSize+1, preEnd, postorder, index+1,postEnd-1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.helper(preorder, postorder, 0, len(preorder)-1, 0, len(postorder)-1)\n",
    "    \n",
    "    def helper(self, preorder, postorder, pre_l, pre_h, post_l, post_h):\n",
    "        if pre_l > pre_h or post_l > post_h:\n",
    "            return None\n",
    "        \n",
    "        if pre_l == pre_h:\n",
    "            return TreeNode(preorder[pre_l])\n",
    "        \n",
    "        index = -1\n",
    "        for i in range(post_l, post_h+1):\n",
    "            if postorder[i] == preorder[pre_l+1]:\n",
    "                index = i\n",
    "        \n",
    "        root = TreeNode(preorder[pre_l])\n",
    "        length = index - post_l + 1\n",
    "        root.left = self.helper(preorder, postorder, pre_l+1, pre_l+length, post_l, index)\n",
    "        root.right = self.helper(preorder, postorder,  pre_l+length+1, pre_h, index+1, post_h-1)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "           \n",
    "        l = postorder.index(preorder[1]) + 1\n",
    "        root.left = self.constructFromPrePost(preorder[1:l+1], postorder[:l])\n",
    "        root.right = self.constructFromPrePost(preorder[l+1:],postorder[l:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        root = TreeNode(preorder[0])\n",
    "        left = preorder[1]\n",
    "        n = len(postorder)\n",
    "        for i in range(len(postorder)):\n",
    "            if postorder[i] == left:\n",
    "                postleft = postorder[0:i+1]\n",
    "                postright = postorder[i+1:n-1]\n",
    "                lenleft = len(postleft)\n",
    "                preleft = preorder [1:lenleft+1]\n",
    "                preright = preorder[lenleft+1:]\n",
    "                break\n",
    "        root.left = self.constructFromPrePost(preleft, postleft)\n",
    "        root.right = self.constructFromPrePost(preright, postright)\n",
    "        return root\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not len(preorder):\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "        partition = postorder.index(preorder[1])\n",
    "        root.left = self.constructFromPrePost(preorder[1:1+partition+1], postorder[:partition])\n",
    "        root.right = self.constructFromPrePost(preorder[1+partition+1:], postorder[partition+1:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not preorder:\n",
    "            return None\n",
    "        test_tree=TreeNode(preorder[0])      \n",
    "        if len(preorder)==1:\n",
    "            return test_tree\n",
    "        \n",
    "        ind1=postorder.index(preorder[1])\n",
    "                                                           \n",
    "        list1=postorder[0:ind1+1]\n",
    "        list3=preorder[1:ind1+2]\n",
    "\n",
    "        list2=preorder[ind1+2:]\n",
    "        list4=postorder[ind1+1:-1]\n",
    "\n",
    " \n",
    "        if list1:\n",
    "            test_tree.left=self.constructFromPrePost(list3,list1)\n",
    "        if list2:\n",
    "            test_tree.right=self.constructFromPrePost(list2,list4)\n",
    "\n",
    "        return test_tree\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return root\n",
    "        \n",
    "        left_root = preorder[1]\n",
    "        left_root_post_index = postorder.index(left_root)\n",
    "        #左子树的nums的个数为（left_root_post_index+1）\n",
    "        root.left = self.constructFromPrePost(preorder[1:left_root_post_index+2],\n",
    "        postorder[:left_root_post_index + 1])\n",
    "        root.right = self.constructFromPrePost(preorder[left_root_post_index+2:],\n",
    "        postorder[left_root_post_index+1:])\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not postorder:\n",
    "            return None        \n",
    "        root = TreeNode(postorder[-1])#preorder[0]\n",
    "        if len(postorder) == 1:\n",
    "            return root \n",
    "\n",
    "        l_index = postorder.index(preorder[1])\n",
    "        # r_index = preorder.index(postorder[-2])\n",
    "        root.left = self.constructFromPrePost(preorder[1:l_index+2], postorder[:l_index+1])\n",
    "        root.right = self.constructFromPrePost(preorder[l_index+2:], postorder[l_index+1:-1])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def createTree(preorder, postorder, n):\n",
    "            if n == 0:\n",
    "                return\n",
    "            node = TreeNode(preorder[0])\n",
    "            if n == 1:\n",
    "                return node\n",
    "            k = 0\n",
    "            # 对于后序序列，0~k是左子树，节点数目为k+1\n",
    "            while preorder[1] != postorder[k]:\n",
    "                k += 1\n",
    "            node.left = createTree(preorder[1:k + 2], postorder[:k + 1], k + 1)\n",
    "            node.right = createTree(preorder[k + 2:], postorder[k + 1:-1], n - k - 2)\n",
    "            return node\n",
    "        return createTree(preorder, postorder, len(preorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        val_to_index = {}\n",
    "\n",
    "        for i in range(len(postorder)):\n",
    "            val_to_index[postorder[i]] = i\n",
    "\n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(preorder)-1, val_to_index)\n",
    "        \n",
    "    \n",
    "    def build(self, preorder, pre_start, pre_end, postorder, post_start, post_end, val_to_index):\n",
    "\n",
    "        if pre_start > pre_end:\n",
    "            return\n",
    "\n",
    "        if pre_start == pre_end:\n",
    "            return TreeNode(preorder[pre_start])\n",
    "        \n",
    "        root_val = preorder[pre_start]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        left_root_val = preorder[pre_start+1]\n",
    "        left_root_idx = val_to_index[left_root_val]\n",
    "        left_num = left_root_idx - post_start + 1\n",
    "\n",
    "        root.left = self.build(preorder, pre_start+1, pre_start+left_num, postorder, post_start, left_root_idx-1, val_to_index)\n",
    "        root.right = self.build(preorder, pre_start+left_num+1, pre_end, postorder, left_root_idx+1, post_end, val_to_index)\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder)==0:\n",
    "            return None\n",
    "        root=TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return root\n",
    "        leftroot=preorder[1]\n",
    "        index=postorder.index(leftroot)\n",
    "        leftsize=index+1\n",
    "        root.left=self.constructFromPrePost(preorder[1:leftsize+1],postorder[:leftsize])\n",
    "        root.right=self.constructFromPrePost(preorder[leftsize+1:],postorder[leftsize:len(preorder)-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "        idx = postorder.index(preorder[1])\n",
    "        root.left = self.constructFromPrePost(preorder[1:idx+2], postorder[:idx+1])\n",
    "        root.right = self.constructFromPrePost(preorder[idx+2:], postorder[idx+1:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0 or len(postorder) == 0:\n",
    "            return None \n",
    "          \n",
    "        root_val = preorder[0]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        if len(preorder) == 1:\n",
    "            postorder_left, postorder_right, preorder_left, preorder_right = [], [], [], []\n",
    "        else: \n",
    "            left_root_val = preorder[1]\n",
    "            left_root_idx_postorder = postorder.index(left_root_val)\n",
    "            \n",
    "            postorder_left = postorder[:left_root_idx_postorder+1]\n",
    "            postorder_right = postorder[left_root_idx_postorder+1:-1]\n",
    "            \n",
    "            preorder_left = preorder[1:len(postorder_left)+1]\n",
    "            preorder_right = preorder[len(postorder_left)+1:]\n",
    "        \n",
    "\n",
    "            # print(root_val, left_root_val, left_root_idx_postorder, preorder_left, preorder_right, postorder_left, postorder_right)\n",
    "\n",
    "\n",
    "        left = self.constructFromPrePost(preorder=preorder_left, postorder=postorder_left)\n",
    "        right = self.constructFromPrePost(preorder=preorder_right, postorder=postorder_right)\n",
    "\n",
    "        root.left = left\n",
    "        root.right = right\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        \n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return node\n",
    "        \n",
    "        k = 0\n",
    "        while preorder[1] != postorder[k]:\n",
    "            k += 1\n",
    "\n",
    "        node.left = self.constructFromPrePost(preorder[1: k+2], postorder[: k+1])\n",
    "        node.right = self.constructFromPrePost(preorder[k+2:], postorder[k+1: -1])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(preorder,postorder):\n",
    "            if not preorder:\n",
    "                return\n",
    "            if len(preorder)==1:\n",
    "                return TreeNode(preorder[0])\n",
    "            # 找到根结点\n",
    "            root=TreeNode(preorder[0])\n",
    "            # 根据前序遍历序列第二个元素，确定后序遍历序列中左子树的范围\n",
    "            left_cnt=postorder.index(preorder[1])+1\n",
    "            root.left=dfs(preorder[1:1+left_cnt],postorder[:left_cnt])\n",
    "            root.right=dfs(preorder[left_cnt+1:],postorder[left_cnt:-1])\n",
    "            return root\n",
    "        return dfs(preorder,postorder)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def constructFromPrePost(self, pre, post):\n",
    "        if not pre: return None\n",
    "        root = TreeNode(pre[0])\n",
    "        if len(pre) == 1: return root\n",
    "\n",
    "        L = post.index(pre[1]) + 1\n",
    "        root.left = self.constructFromPrePost(pre[1:L+1], post[:L])\n",
    "        root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        root_val = preorder[0]\n",
    "\n",
    "        l_preorder = preorder[1:postorder.index(preorder[1])+2]\n",
    "        r_preorder = preorder[postorder.index(preorder[1])+2:]\n",
    "        l_postorder = postorder[:len(l_preorder)]\n",
    "        r_postorder = postorder[len(l_preorder):-1]\n",
    "        root = TreeNode(root_val)\n",
    "        l = self.constructFromPrePost(l_preorder, l_postorder)\n",
    "        r = self.constructFromPrePost(r_preorder, r_postorder)\n",
    "\n",
    "        root.left = l\n",
    "        root.right = r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)\n",
    "    \n",
    "    def build(self, preorder, pre_start, pre_end, postorder, pos_start, pos_end):\n",
    "        if pre_start > pre_end:\n",
    "            return None\n",
    "        \n",
    "        if pre_start == pre_end:\n",
    "            return TreeNode(preorder[pre_start])\n",
    "        \n",
    "        root_val = preorder[pre_start]\n",
    "        left_root_val = preorder[pre_start + 1]\n",
    "        left_index = postorder.index(left_root_val)\n",
    "        left_size = left_index - pos_start + 1\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        root.left = self.build(preorder, pre_start + 1, pre_start + left_size, postorder, pos_start, left_index)\n",
    "        root.right = self.build(preorder, pre_start + left_size + 1, pre_end, postorder, left_index + 1, pos_end - 1)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        \n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return node\n",
    "        \n",
    "        k = 0\n",
    "        while preorder[1] != postorder[k]:\n",
    "            k += 1\n",
    "\n",
    "        node.left = self.constructFromPrePost(preorder[1: k+2], postorder[: k+1]) # 注意k+2\n",
    "        node.right = self.constructFromPrePost(preorder[k+2:], postorder[k+1: -1])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        rt = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return rt\n",
    "        t = preorder[1]\n",
    "        pt = postorder.index(t)\n",
    "        rt.left = self.constructFromPrePost(preorder[1:pt + 2], postorder[:pt + 1])\n",
    "        rt.right = self.constructFromPrePost(preorder[pt + 2:], postorder[pt + 1:-1])\n",
    "        return rt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not preorder:\n",
    "            return None\n",
    "        test_tree=TreeNode(preorder[0])      \n",
    "        if len(preorder)==1:\n",
    "            return test_tree\n",
    "        \n",
    "        ind1=postorder.index(preorder[1])\n",
    "                                                           \n",
    "        list1=postorder[0:ind1+1]\n",
    "        list3=preorder[1:ind1+2]\n",
    "\n",
    "        list2=preorder[ind1+2:]\n",
    "        list4=postorder[ind1+1:-1]\n",
    "\n",
    "\n",
    "        test_tree.left=self.constructFromPrePost(list3,list1)\n",
    "\n",
    "        test_tree.right=self.constructFromPrePost(list2,list4)\n",
    "\n",
    "        return test_tree\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, pre: List[int], post: List[int]) -> Optional[TreeNode]:\n",
    "        if not pre: return None\n",
    "        root = TreeNode(pre[0])\n",
    "        if len(pre) == 1: return root\n",
    "\n",
    "        L = post.index(pre[1]) + 1\n",
    "        root.left = self.constructFromPrePost(pre[1:L+1], post[:L])\n",
    "        root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.postVal2Idx = {}\n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        if preStart == preEnd:\n",
    "            return TreeNode(preorder[preStart])\n",
    "        root_val = preorder[preStart]\n",
    "        left_root_val = preorder[preStart+1]\n",
    "        index = self.postVal2Idx[left_root_val]\n",
    "        left_size = index - postStart + 1\n",
    "        root = TreeNode(root_val)\n",
    "        root.left = self.build(preorder, preStart+1, preStart + left_size, postorder, postStart, index)\n",
    "        root.right = self.build(preorder, preStart + left_size + 1, preEnd, postorder, index+1, postEnd-1)\n",
    "        return root\n",
    "        \n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        for i, val in enumerate(postorder):\n",
    "            self.postVal2Idx[val] = i\n",
    "        # for i in range(len(postorder)):\n",
    "        #     self.postVal2Idx[postorder[i]] = i\n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(pre, post):\n",
    "            if not pre: \n",
    "                return None\n",
    "            root = TreeNode(pre[0])\n",
    "            if len(pre) == 1: \n",
    "                return root\n",
    "\n",
    "            L = post.index(pre[1]) + 1\n",
    "            root.left = dfs(pre[1:L+1], post[:L])\n",
    "            root.right = dfs(pre[L+1:], post[L:-1])\n",
    "            return root\n",
    "        return dfs(preorder, postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        #根据前序与后序的性质递归地连接\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root=TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return root\n",
    "        j=postorder.index(preorder[1])\n",
    "        root.left=self.constructFromPrePost(preorder[1:j+2],postorder[:j+1])\n",
    "        root.right=self.constructFromPrePost(preorder[j+2:],postorder[j+1:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode()\n",
    "        def dfs(preorder, postorder, root):\n",
    "            if not (preorder and postorder):\n",
    "                return\n",
    "            root.val = preorder[0]\n",
    "            if len(preorder) == 1:\n",
    "                return\n",
    "            left_root = preorder[1]\n",
    "            left_root_index = postorder.index(left_root)\n",
    "            \n",
    "            left_postorder = postorder[:-1][:left_root_index+1]\n",
    "            right_postorder = postorder[:-1][left_root_index+1:]\n",
    "\n",
    "            left_preorder = preorder[1:][:len(left_postorder)]\n",
    "            right_preorder = preorder[1:][len(left_postorder):]\n",
    "\n",
    "            if left_preorder:\n",
    "                root.left = TreeNode()\n",
    "                dfs(left_preorder, left_postorder, root.left)\n",
    "\n",
    "            if right_preorder:\n",
    "                root.right = TreeNode()\n",
    "                dfs(right_preorder, right_postorder, root.right)\n",
    "\n",
    "        dfs(preorder, postorder, root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def tree(preorder, postorder):\n",
    "            if not preorder or not postorder:\n",
    "                return\n",
    "            root = TreeNode(preorder[0])\n",
    "            if len(preorder)>=2:\n",
    "                val = preorder[1]\n",
    "                idx = postorder.index(val)\n",
    "                l_pre = preorder[1:idx+2]\n",
    "                l_post = postorder[:idx+1]\n",
    "                r_pre = preorder[idx+2:]\n",
    "                r_post = postorder[idx+1:-1]\n",
    "                root.left = tree(l_pre, l_post)\n",
    "                root.right = tree(r_pre, r_post)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return tree(preorder, postorder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        root = TreeNode(preorder[0])\n",
    "        left = preorder[1]\n",
    "        index = postorder.index(left)\n",
    "        root.left = self.constructFromPrePost(preorder[1:index + 2], postorder[:index + 1])\n",
    "        root.right = self.constructFromPrePost(preorder[index + 2:], postorder[index + 1:-1])\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder or not postorder:\n",
    "            return\n",
    "        num = preorder[0]\n",
    "        root = TreeNode(num)\n",
    "        if len(preorder)>=2:\n",
    "            left_root = preorder[1]\n",
    "            index = postorder.index(left_root)\n",
    "            root.left = self.constructFromPrePost(preorder[1:index+2],postorder[:index+1])\n",
    "            root.right = self.constructFromPrePost(preorder[index+2:],postorder[index+1:-1])\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        self.map = {num:i for i, num in enumerate(postorder)}\n",
    "\n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder)-1)\n",
    "\n",
    "    \n",
    "    def build(self, preorder, prestart, preend, inorder, instart, inend):\n",
    "        if prestart > preend:\n",
    "            return None\n",
    "        if prestart == preend:\n",
    "            return TreeNode(preorder[prestart]) \n",
    "\n",
    "        root_val = preorder[prestart]\n",
    "        root = TreeNode(root_val) \n",
    "         \n",
    "        next_root_val = preorder[prestart+1]\n",
    "        index = self.map[next_root_val]\n",
    "        size = index - instart + 1\n",
    "        root.left = self.build(preorder, prestart+1, prestart+size, inorder, instart, index)\n",
    "        root.right = self.build(preorder, prestart+size+1, preend, inorder, index+1, inend-1)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-172f0/\n",
    "# 二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。\n",
    "# 之前都有中序遍历，所以靠中序的root的index。这道题没有中序，所以就靠前序的第一个left_val,再去后序找left_index\n",
    "# 前序+后序：没有唯一答案\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder or not postorder:\n",
    "            return None\n",
    "        # if len(preorder) == 1 or len(postorder) == 1: # 不能写在这，只能写在下面那个函数里\n",
    "        #     return TreeNode(preorder[0])\n",
    "\n",
    "        pre_s = 0\n",
    "        pre_e = len(preorder) - 1\n",
    "        post_s = 0\n",
    "        post_e = len(postorder) - 1\n",
    "\n",
    "        return self.build(preorder, pre_s, pre_e, postorder, post_s, post_e)\n",
    "\n",
    "    def build(self, preorder, pre_s, pre_e, postorder, post_s, post_e):\n",
    "        if pre_s > pre_e:\n",
    "            return None\n",
    "\n",
    "        # 重点，意思就是只有一个数字,只能写在这，因为循环到最后可能两者也会相等\n",
    "        # 必须写在这，否则后面preorder[pre_s + 1]可能会溢出边界\n",
    "        if pre_s == pre_e:\n",
    "            return TreeNode(preorder[pre_s])\n",
    "        \n",
    "        root_val = preorder[pre_s]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        left_val = preorder[pre_s + 1]\n",
    "        left_index = postorder.index(left_val)\n",
    "        leftsize = left_index - post_s + 1\n",
    "        # 这里加1也是重点。把后序的图画出来，如post_s = 0,left_index=5,说明左子树有0 1 2 3 4 5，一共6个数，但是5-0=5，所以要加1\n",
    "\n",
    "        # 递归构造左右子树\n",
    "        root.left = self.build(preorder, pre_s + 1, pre_s + 1 + leftsize - 1, postorder, post_s, left_index)\n",
    "        root.right = self.build(preorder, pre_s + leftsize + 1, pre_e, postorder, left_index + 1, post_e - 1)\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         # 存储 postorder 中值到索引的映射\n",
    "#         self.valToIndex = {}\n",
    "\n",
    "#     def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "#         for i in range(len(postorder)):\n",
    "#             self.valToIndex[postorder[i]] = i\n",
    "#         return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)\n",
    "\n",
    "#     # 根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd] 构建二叉树，并返回根节点。\n",
    "#     def build(self, preorder: List[int], preStart: int, preEnd: int, postorder: List[int], postStart: int, postEnd: int) -> TreeNode:\n",
    "#         if preStart > preEnd:\n",
    "#             return None\n",
    "#         if preStart == preEnd:\n",
    "#             return TreeNode(preorder[preStart])\n",
    "\n",
    "#         # root 节点对应的值就是前序遍历数组的第一个元素\n",
    "#         rootVal = preorder[preStart]\n",
    "#         # root.left 的值是前序遍历第二个元素\n",
    "#         # 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点\n",
    "#         # 确定 preorder 和 postorder 中左右子树的元素区间\n",
    "#         leftRootVal = preorder[preStart + 1]\n",
    "#         # leftRootVal 在后序遍历数组中的索引\n",
    "#         index = self.valToIndex[leftRootVal]\n",
    "#         # 左子树的元素个数\n",
    "#         leftSize = index - postStart + 1\n",
    "\n",
    "#         # 先构造出当前根节点\n",
    "#         root = TreeNode(rootVal)\n",
    "#         # 递归构造左右子树\n",
    "#         # 根据左子树的根节点索引和元素个数推导左右子树的索引边界\n",
    "#         root.left = self.build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index)\n",
    "#         root.right = self.build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1)\n",
    "\n",
    "#         return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        if len(preorder) == 1:  # 数组长度为1时, 直接返回即可\n",
    "            return TreeNode(preorder[0])\n",
    "            \n",
    "        root = TreeNode(preorder[0])  # 根据前序数组的第1个元素, 创建根节点\n",
    "        left_count = postorder.index(preorder[1]) + 1  # 根据前序数组的第2个元素确定后序数组的左子树范围（左子树的节点个数）\n",
    "        \n",
    "        # 递归执行前序数组左边、后序数组左边。前序数组右边，后序数组右边\n",
    "        root.left = self.constructFromPrePost(preorder[1: left_count+1], postorder[: left_count])\n",
    "        root.right = self.constructFromPrePost(preorder[left_count+1:], postorder[left_count: -1])\n",
    "        \n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def sub(pre, prestart, preend, post, poststart, postend):\n",
    "            if prestart > preend:\n",
    "                return None\n",
    "            if prestart == preend:\n",
    "                return TreeNode(pre[prestart])\n",
    "            root = TreeNode(pre[prestart])\n",
    "            index = post.index(pre[prestart + 1])\n",
    "            left_size = index - poststart + 1\n",
    "            root.left = sub(pre, prestart + 1, prestart + left_size, post, poststart, index - 1)\n",
    "            root.right = sub(pre, prestart + left_size + 1, preend, post, index + 1, postend)\n",
    "            return root\n",
    "        return sub(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not preorder:\n",
    "            return None\n",
    "        test_tree=TreeNode(preorder[0])      \n",
    "        if len(preorder)==1:\n",
    "            return test_tree\n",
    "        \n",
    "        ind1=postorder.index(preorder[1])\n",
    "                                                           \n",
    "        list1=postorder[0:ind1+1]\n",
    "        list3=preorder[1:ind1+2]\n",
    "\n",
    "        list2=preorder[ind1+2:]\n",
    "        list4=postorder[ind1+1:-1]\n",
    "\n",
    "        # test_tree.left=self.constructFromPrePost(list3,list1)\n",
    "        # test_tree.right=self.constructFromPrePost(list2,list4)\n",
    "        if list1:\n",
    "            test_tree.left=self.constructFromPrePost(list3,list1)\n",
    "        if list2:\n",
    "            test_tree.right=self.constructFromPrePost(list2,list4)\n",
    "\n",
    "        return test_tree\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(postorder)==0:\n",
    "            return\n",
    "        if len(postorder)==1:\n",
    "            return TreeNode(postorder[0])\n",
    "        idx=postorder.index(preorder[1])\n",
    "        return TreeNode(postorder[-1],self.constructFromPrePost(preorder[1:2+idx],postorder[:idx+1]),self.constructFromPrePost(preorder[2+idx:],postorder[idx+1:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def helpConstruct(preorder, prelow, prehigh, postorder,postlow, posthigh):\n",
    "            if prelow < 0 or postlow < 0 or prehigh >= len(preorder) or posthigh >= len(postorder) or prelow > prehigh or postlow > posthigh:\n",
    "                return None\n",
    "\n",
    "            rootVal = preorder[prelow]\n",
    "            root = TreeNode(rootVal)\n",
    "            \n",
    "            if prelow + 1 > prehigh:\n",
    "                return root\n",
    "            leftRootVal = preorder[prelow+1]\n",
    "            # 在 postorder 中找 leftRootVal 所在的索引\n",
    "            leftRootPostIndex = postlow\n",
    "            for i in range(postlow, posthigh+1):\n",
    "                if postorder[i] == leftRootVal:\n",
    "                    leftRootPostIndex = i\n",
    "            \n",
    "            leftSize = leftRootPostIndex - postlow + 1\n",
    "\n",
    "            # 构造左子树和右子树\n",
    "            root.left = helpConstruct(preorder, prelow+1, prelow + leftSize, postorder, postlow, leftRootPostIndex)\n",
    "            root.right = helpConstruct(preorder, prelow + leftSize+1, prehigh, postorder,leftRootPostIndex+1, posthigh-1)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return helpConstruct(preorder,0,len(preorder)-1,postorder,0, len(postorder)-1)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def construct(preorder, postorder):\n",
    "            if len(preorder) == 0:\n",
    "                return\n",
    "            if len(preorder) == 1:\n",
    "                return TreeNode(preorder[0])\n",
    "            root_val = preorder[0]\n",
    "            left_root = preorder[1]\n",
    "            left_idx = postorder.index(left_root)\n",
    "            left_postorder = postorder[:left_idx+1]\n",
    "            right_postorder = postorder[left_idx+1:-1]\n",
    "\n",
    "            right_root = postorder[-2]\n",
    "            if right_root==left_root:\n",
    "                right_postorder=right_preorder=[]\n",
    "                left_preorder=preorder[1:]\n",
    "            else:\n",
    "                right_idx = preorder.index(right_root)\n",
    "                left_preorder = preorder[1:right_idx]\n",
    "                right_preorder = preorder[right_idx:]\n",
    "            return TreeNode(\n",
    "                root_val,\n",
    "                construct(left_preorder, left_postorder),\n",
    "                construct(right_preorder, right_postorder)\n",
    "            )\n",
    "        return construct(preorder, postorder)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder or not postorder:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "        index_left = postorder.index(preorder[1])\n",
    "        if len(preorder) > index_left + 2:\n",
    "            index_right = preorder.index(postorder[-2])\n",
    "\n",
    "            root.left = self.constructFromPrePost(preorder[1:index_right], postorder[:index_left + 1])\n",
    "            root.right = self.constructFromPrePost(preorder[index_right:], postorder[index_left + 1 : -1])\n",
    "        else:\n",
    "            root.left = self.constructFromPrePost(preorder[1:], postorder[:index_left + 1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\r\n",
    "        def make(i,j,k):\r\n",
    "            if k==0:\r\n",
    "                return None\r\n",
    "            root=TreeNode(preorder[i])\r\n",
    "            if k==1:\r\n",
    "                return root\r\n",
    "            kk=postorder.index(preorder[i+1],j)-j+1\r\n",
    "            root.left=make(i+1,j,kk)\r\n",
    "            root.right=make(i+1+kk,j+kk,k-kk-1)\r\n",
    "            return root\r\n",
    "\r\n",
    "        return make(0,0,len(preorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\r\n",
    "        if not preorder:\r\n",
    "            return None\r\n",
    "        parent=TreeNode(preorder[0])\r\n",
    "        if len(preorder)==1:\r\n",
    "            return parent\r\n",
    "        L=postorder.index(preorder[1])+1\r\n",
    "        parent.left=self.constructFromPrePost(preorder[1:L+1],postorder[:L])\r\n",
    "        parent.right=self.constructFromPrePost(preorder[L+1:],postorder[L:-1])\r\n",
    "        return parent\r\n",
    "    \r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        \n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "        \n",
    "        # postorder中左子树根出现在左子树节点最后\n",
    "        # 根据index可以确定左子树长度L\n",
    "        L = postorder.index(preorder[1]) + 1\n",
    "\n",
    "        root.left = self.constructFromPrePost(preorder[1:L+1], postorder[:L])\n",
    "        root.right = self.constructFromPrePost(preorder[L+1:], postorder[L:-1])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(preorder[0])\n",
    "        \n",
    "        if len(preorder) ==1:\n",
    "            return root\n",
    "        left_root_index = postorder.index(preorder[1])\n",
    "\n",
    "        left_preorder = preorder[1: 2+ left_root_index]\n",
    "        left_postorder = postorder[:left_root_index + 1]\n",
    "        right_preorder = preorder[2+ left_root_index:]\n",
    "        right_postorder = postorder[left_root_index + 1: -1]\n",
    "\n",
    "        root.left = self.constructFromPrePost(left_preorder, left_postorder)\n",
    "        root.right = self.constructFromPrePost(right_preorder, right_postorder)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        tree = TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return tree\n",
    "        i = postorder.index(preorder[1])\n",
    "        left_pre = preorder[1:i+2]\n",
    "        left_post = postorder[:i+1]\n",
    "        right_pre = preorder[i+2:]\n",
    "        right_post = postorder[i+1:-1]\n",
    "        print(left_pre,left_post,right_pre,right_post)\n",
    "        tree.left = self.constructFromPrePost(left_pre,left_post)\n",
    "        tree.right = self.constructFromPrePost(right_pre,right_post)\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        dic = {}\n",
    "        for i, ele in enumerate(postorder):\n",
    "            dic[ele] = i\n",
    "        def judge(pre_begin, pre_end, post_begin, post_end):\n",
    "            if pre_begin > pre_end:\n",
    "                return\n",
    "            if pre_begin == pre_end:\n",
    "                return TreeNode(preorder[pre_begin])\n",
    "\n",
    "            root = TreeNode(preorder[pre_begin])\n",
    "            first_left = preorder[pre_begin + 1]\n",
    "            ind = dic[first_left]\n",
    "            root.left = judge(pre_begin + 1, pre_begin + ind - post_begin + 1, post_begin, ind)\n",
    "            root.right = judge(pre_begin + ind - post_begin + 2, pre_end, ind + 1, post_end - 1)\n",
    "            return root\n",
    "        return judge(0, len(preorder) - 1, 0, len(postorder) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def constructFromPrePost(self, pre, post):\n",
    "        post_map = dict()\n",
    "        for i,val in enumerate(post):\n",
    "            post_map[val] = i\n",
    "        def make(i0, i1, N):\n",
    "            if N == 0: return None\n",
    "            root = TreeNode(pre[i0])\n",
    "            if N == 1: return root\n",
    "\n",
    "            L = post_map[pre[i0+1]] + 1 - i1\n",
    "\n",
    "            root.left = make(i0 + 1, i1, L)\n",
    "            root.right = make(i0 + L + 1, i1 + L, N - 1 - L)\n",
    "            return root\n",
    "\n",
    "        return make(0, 0, len(pre))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def createTree(preorder, postorder, n):\n",
    "            if n == 0:\n",
    "                return None\n",
    "\n",
    "            node = TreeNode(preorder[0])\n",
    "            if n == 1:\n",
    "                return node\n",
    "            \n",
    "            k = 0\n",
    "            while preorder[1] != postorder[k]:\n",
    "                k += 1\n",
    "            \n",
    "            node.left = createTree(preorder[1:k+2], postorder[:k+1], k+1)  # 左子树长度为 k+1\n",
    "            node.right = createTree(preorder[k+2:], postorder[k+1:n-2], n-k-2)\n",
    "            return node\n",
    "        return createTree(preorder, postorder, len(preorder))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        val2idx_post = {val:idx for idx, val in enumerate(postorder)}\n",
    "\n",
    "        def _construct(pre_start, pre_end, post_start, post_end):\n",
    "            if pre_start == pre_end:\n",
    "                return None\n",
    "\n",
    "            root_val = preorder[pre_start]\n",
    "            if pre_start == pre_end - 1:\n",
    "                return TreeNode(root_val)\n",
    "\n",
    "            post_idx = val2idx_post[preorder[pre_start + 1]]\n",
    "            left_len = post_idx - post_start + 1\n",
    "\n",
    "            left = _construct(pre_start + 1, pre_start + left_len + 1,\n",
    "                                post_start, post_start + left_len + 1)\n",
    "            right = _construct(pre_start + left_len + 1, pre_end,\n",
    "                                post_idx + 1, post_end - 1)\n",
    "            return TreeNode(root_val, left, right)\n",
    "\n",
    "        return _construct(0, len(preorder), 0, len(postorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        # x [l] [r]\n",
    "        # [l] [r] x\n",
    "\n",
    "        # x [l ...] [r ... ]\n",
    "        # [... l]   [.... r] x\n",
    "\n",
    "        map = dict()\n",
    "        for i, x in enumerate(preorder):\n",
    "            map[x] = i\n",
    "\n",
    "        n = len(preorder)\n",
    "        def dfs(i,j, a,b) -> Optional[TreeNode]:\n",
    "            if i > j or a > b:\n",
    "                return None  \n",
    "\n",
    "            root = preorder[i]\n",
    "            if j-i+1 == 1:\n",
    "                return TreeNode(root, None, None)\n",
    "            \n",
    "\n",
    "            # x [l, ] [r   ]\n",
    "            # [   l] [  r] x\n",
    "            y = map[postorder[b-1]] \n",
    "            t = y - i - 1 #要求>0\n",
    "            \n",
    "            \n",
    "            \n",
    "            # [x, j] [a+l, b]\n",
    "            left = dfs(i+1, y-1, a, a+t-1) \n",
    "            right = dfs(y, j, a+t, b-1)\n",
    "            return TreeNode(root, left, right)\n",
    "        return dfs(0, n-1, 0, n-1)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        # def createTree(preorder, postorder, n):\n",
    "        #     if n == 0:\n",
    "        #         return\n",
    "        #     node = TreeNode(preorder[0])\n",
    "        #     if n == 1:\n",
    "        #         return node\n",
    "        #     k = 0\n",
    "        #     # 对于后序序列，0~k是左子树，节点数目为k+1\n",
    "        #     while preorder[1] != postorder[k]:\n",
    "        #         k += 1\n",
    "        #     node.left = createTree(preorder[1:k + 2], postorder[:k + 1], k + 1)\n",
    "        #     node.right = createTree(preorder[k + 2:], postorder[k + 1:-1], n - k - 2)\n",
    "        #     return node\n",
    "        # return createTree(preorder, postorder, len(preorder))\n",
    "\n",
    "        # def recur(root, left, right):\n",
    "        #     if left > right: return \n",
    "        #     node = TreeNode(preorder[root])\n",
    "        #     if root == len(preorder) - 1:\n",
    "        #         return node\n",
    "        #     i = dic[preorder[root + 1]]\n",
    "        #     if left <= i <= right:\n",
    "        #         node.left = recur(root + 1, left, i)\n",
    "        #         node.right = recur(root + i - left + 2, i + 1, right - 1)\n",
    "        #     return node\n",
    "        # dic, preorder = {}, preorder\n",
    "        # for i in range(len(postorder)):\n",
    "        #     dic[postorder[i]] = i\n",
    "        # return recur(0, 0, len(postorder) - 1)\n",
    "\n",
    "        def recur(root, left, right):\n",
    "            if left > right: return\n",
    "            node = TreeNode(preorder[root])\n",
    "            if root == len(preorder) - 1: return node\n",
    "            i = dic[preorder[root + 1]]\n",
    "            if left <= i <= right:\n",
    "                node.left = recur(root + 1, left, i)\n",
    "                node.right = recur(root + i - left + 2, i + 1, right - 1)\n",
    "            return node\n",
    "        dic, preorder = {}, preorder\n",
    "        for i in range(len(postorder)):\n",
    "            dic[postorder[i]] = i\n",
    "        return recur(0, 0, len(postorder) - 1)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 构造hash查找index\n",
    "        self.postorderDict = {}\n",
    "\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        # 构造hash\n",
    "        for i in range(len(postorder)):\n",
    "            self.postorderDict[postorder[i]] = i\n",
    "        \n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder)-1)\n",
    "    \n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        # 构造辅助递归函数build\n",
    "        # base case\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        if preStart == preEnd:\n",
    "            return TreeNode(preorder[preStart])\n",
    "        # 构造根节点\n",
    "        rootValue = preorder[preStart]\n",
    "        rootLeftValue = preorder[preStart+1]\n",
    "        root = TreeNode(rootValue)\n",
    "        # 查找左子树的root值\n",
    "        print(preStart, preEnd, len(preorder))\n",
    "        \n",
    "        # 在postorder中查询左子树root值的索引\n",
    "        index = self.postorderDict[rootLeftValue]\n",
    "        # 左子树的长度\n",
    "        leftRootLength = index - postStart + 1\n",
    "        # 递归构造左子树\n",
    "        root.left = self.build(preorder, preStart+1, preStart+leftRootLength, postorder, postStart, index)\n",
    "        # 递归构造右子树\n",
    "        root.right = self.build(preorder, preStart+leftRootLength+1, preEnd, postorder, index+1, postEnd-1)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(pre,post):\n",
    "            if len(pre)==0:\n",
    "                return None\n",
    "            if len(pre)==1:\n",
    "                return TreeNode(pre[0])\n",
    "            rootVal=pre[0]\n",
    "            leftRootVal=pre[1]\n",
    "            leftLength=post.index(leftRootVal)+1\n",
    "            leftPre=pre[1:leftLength+1]\n",
    "            rightPre=pre[leftLength+1:]\n",
    "\n",
    "            leftPost=post[0:leftLength]\n",
    "            rightPost=post[leftLength:len(post)-1]\n",
    "            midNode=TreeNode(rootVal)\n",
    "            leftNode=build(leftPre,leftPost)\n",
    "            rightNode=build(rightPre,rightPost)\n",
    "            midNode.left=leftNode\n",
    "            midNode.right=rightNode\n",
    "            return midNode\n",
    "        return build(preorder,postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(preStart, preEnd, postStart, postEnd):\n",
    "            if preStart > preEnd:\n",
    "                return None\n",
    "            elif preStart == preEnd:\n",
    "                return TreeNode(preorder[preStart])\n",
    "            \n",
    "            root = TreeNode(preorder[preStart])\n",
    "            leftroot_val = preorder[preStart + 1]\n",
    "            index = value2index[leftroot_val]\n",
    "            leftsize = index - postStart + 1\n",
    "            root.left = build(preStart + 1, preStart + leftsize, postStart, index)\n",
    "            root.right = build(preStart + leftsize + 1, preEnd, index + 1, postEnd)\n",
    "            return root\n",
    "        \n",
    "        value2index = dict()\n",
    "        for i in range(len(postorder)):\n",
    "            value2index[postorder[i]] = i\n",
    "        return build(0, len(preorder) - 1, 0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        hash_table = {val: i for i, val in enumerate(postorder)}\n",
    "\n",
    "        def build(pre_left: int, pre_right: int, post_left: int, post_right: int) -> Optional[TreeNode]:\n",
    "            if pre_left > pre_right:\n",
    "                return\n",
    "            root = TreeNode(val=preorder[pre_left])\n",
    "            # 不能省！！！因为左子节点不一定存在！！\n",
    "            if pre_left == pre_right:\n",
    "                return root\n",
    "            left_val = preorder[pre_left + 1]\n",
    "            post_left_pos = hash_table[left_val]\n",
    "            left_sublen = post_left_pos - post_left + 1\n",
    "\n",
    "            root.left = build(pre_left + 1, pre_left + left_sublen, post_left, post_left_pos)\n",
    "            root.right = build(pre_left + left_sublen + 1, pre_right, post_left_pos + 1, post_right - 1)\n",
    "\n",
    "            return root\n",
    "\n",
    "        ln = len(preorder)\n",
    "        return build(0, ln - 1, 0, ln - 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
